RT_SECURE_NO_WARNINGS 1

#include <iostream>

using namespace std;

int PartSort(int *arr,int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		while (left < right && arr[right] >= arr[keyi])
			right--;
		while (left < right && arr[left] <= arr[keyi])
			left++;

		swap(arr[left], arr[right]);
		//Swap(arr, &left, &right);
	}
	swap(arr[keyi], arr[left]);
	return left;
}

void QuickSort(int* arr, int begin, int end)
{
	if (begin >= end)
		return;

	int Keyi = PartSort(arr, begin, end);
	QuickSort(arr, begin, Keyi - 1);
	QuickSort(arr, Keyi + 1, end);
}


int main()
{
	int arr[] = {1,4,3,5,2,6};
	for (auto e : arr)
	{
		cout << e << " ";
	}
	cout << endl;

	QuickSort(arr, 0, 5);
	for (auto e : arr)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}
